package com.zwj.interview.动态规划;


import java.util.Arrays;

/**
 * 输入一个数组表示某条街道上的一排房屋内财产的数量。如果这条街道上相邻的两幢房屋被盗就会自动触发报警系统。
 * 请计算小偷在这条街道上最多能偷取到多少财产。例如，街道上5幢房屋内的财产用数组[2，3，4，5，3]表示，
 * 如果小偷到下标为0、2和4的房屋内盗窃，那么他能偷取到价值为9的财物，这是他在不触发报警系统的情况下能偷取到的最多的财物
 */
public class 打家劫舍 {

     int[] memo;
    /**
     * 小偷在标号为i的房屋前有两个选择。一个选择是他进去偷东西。由于街道上有报警系统，
     * 因此他不能进入相邻的标号为i-1的房屋内偷东西，之前他最多能偷取的财物的最大值是f（i-2）。
     * 因此，小偷如果进入标号为i的房屋并盗窃，他最多能偷得f（i-2）+nums[i]（nums是表示房屋内财物数量的数组）。
     * 另一个选择是小偷不进入标号为i的房屋，那么他可以进入标号为i-1的房屋内偷东西，因此此时他最多能偷取的财物的数量为f（i-1）。
     * 那么小偷在到达标号为i的房屋时他能偷取的财物的最大值就是两个选项的最大值，即f（i）=max（f（i-2）+nums[i]，f（i-1）），
     * 这就是解决这个问题的状态转移方程
     *
     * 我们定义方程：
     * dp(nums,start)=x表示，从nums[start]开始做选择，可以获得的最多的金额为x
     */
    public int rob(int[] nums) {
        //特殊情况
        if(nums==null || nums.length==0 ){
            return 0;
        }
        int[] dp=new int[nums.length];
        //如果房间只有一间房屋的话，那么就偷盗这件房屋
        dp[0]=nums[0];
        //只有两间房屋的时候，就悬价值大的一间偷盗
        dp[1]=Math.max(nums[0],nums[1]);
        //当房屋大于2间的时候
        for(int i=2;i<nums.length;i++){
            //到了下标为i的房间，要么选择偷，要么选择不偷
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }




}
